/*
Source : https://leetcode.com/problems/fraction-to-recurring-decimal/
Author : nflush@outlook.com
Date   : 2016-07-07
*/

/*
166. Fraction to Recurring Decimal 
    Total Accepted: 33418
    Total Submissions: 214266
    Difficulty: Medium

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

    Given numerator = 1, denominator = 2, return "0.5".
    Given numerator = 2, denominator = 1, return "2".
    Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
*/

class Solution {
private:
    long long int gcd(long long int a, long long int b){
        if(b == 0){
            return a;
        }
        return gcd(b, a % b);
    }
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) return "0";
        char a[3000] = ".";
        long long int d = denominator;
        long long int n = numerator;
        bool mis = (d*n < 0);
        if (d < 0){
            d = 0 - d;
        }
        if (n < 0){
            n = 0 - n;
        }
        long long int y = n % d;
        long long int x = n/d;
        int  i = 1;
        string ret = mis?"-"+std::to_string(x):std::to_string(x);
        if (y){
            unordered_map<long long int, int> m;
            long long int g = gcd(d, y);
            y /= g;
            d /= g;
            while(y && m.find(y) == m.end()) {
                y *= 10;
                a[i++] = '0' + y / d;
                m[y/10] = i;
                y = y % d;
            }
            if (y != 0){
                int start = m[y] - 1;
                int len  = i - start;
                memmove(a + start + 1, a+start, len);
                a[start] = '(';
                i++;
                a[i] = ')';
                i++;
            }
            a[i] = '\0';
            return ret + a;
        }
        return ret;
    }
};


